#include "stdio.h"
#include "List.h"


List l;
List l1;
List l2;

/**
 * P30.2-1
 * 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除元素的值，空出的位置由
 * 最后一个元素填补，若顺序表为空，则显示出错信息并退出运行
 * @return 被删除元素的值
 */
bool SortDelete(int &min){

    if (l.l.length <= 0 )
        return false;
    min = l.l.data[0];
    int minIndex = 0;
    for (int i = 0; i < l.l.length - 1; i++) {
        if (min > l.l.data[i+1]){
            min = l.l.data[i+1];
            minIndex = i + 1;
        }
    }
    l.l.data[minIndex] = l.l.data[l.l.length-1];
    l.l.data[l.l.length-1] = 0;
    l.l.length --;
    return true;
}

/**
 * P30.2-2
 * 设计一个高效算法，将顺序表L的所有元素逆序，要求算法的空间复杂度为0(1);
 */
void ReverseOrder(){

    // 二分法 左右两边互换
    for (int i = 0; i < l.l.length / 2 ; i++) {
        // 互换
        l.l.data[i] = l.l.data[i] + l.l.data[l.l.length - 1 - i];
        l.l.data[l.l.length - 1 - i] = l.l.data[i] - l.l.data[l.l.length - 1 - i];
        l.l.data[i] = l.l.data[i] - l.l.data[l.l.length - 1 - i];
    }
}

/**
 * /**
 * P30.2-3
 * 对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，
 * 该算法删除线性表中所有值为x的数据元素
 * @param x
 *
 */
void DelMatch(int x){
    int size = 0;
    int findCount = 0;
    for (int i = 0; i < l.l.length; i++) {
        if (l.l.data[i] == x) size ++;
        if (size > 0) {
            if (i + size > l.l.length) findCount ++;
            l.l.data[i] = l.l.data[i] + l.l.data[i + size];
            l.l.data[i + size] = l.l.data[i] - l.l.data[i + size];
            l.l.data[i] = l.l.data[i] - l.l.data[i + size];
        }
    }
    l.l.length -= findCount;
}

/**
 * （2010年统考真题）
 * 设将n (n > 1)个整数存放在一维数组R中，设计一个在时间和空间
 * 两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n)个位置，既
 * 将R中的数据由（X0,X1....,Xn-1）变换为（Xp,Xp+1....,X0,X1...Xp-1)
 * 1).给出算法的基本设计思想
 * 2).说明你所设计算法的时间复杂度和空间复杂度
 * @param p
 */
void LeftMove(int p){
    // 算出左移后 会被放到最前面的序列。 Xp...Xn-1
    int size = l.l.length - p - 1;

    // 临时数组的索引
    int index = 0;

    // 复制一个临时数组
    int *data = (int *)malloc(l.l.length * sizeof (int));

    // 先将原数组的 Xp...Xn-1 按顺序放到 X0...Xp-1
    for (int i = p; i < size + p + 1; i++) {
        data[index] = l.l.data[i];
        index++;
    }

    // 将原数组的 X0...Xp-1 按顺序放到 Xp...Xn-1
    for (int i = 0; i < p; i++) {
        data[index] = l.l.data[i];
        index++;
    }

    // 临时数组的值放入原数组
    l.l.data = data;
}

/**
 * 【2011 统考真题】一个长度为 L（L ≥ 1）的升序序列 S，处在第[L/2]个位置的数称为S
 * 的中位数。例如，若序列 S1=(8,13,15,17,19)，则S1的中位数是15，两个序列的中位
 * 数是含它们所有元素的升序序列的中位数。例如，若 S2=(2,4,5,11,20)，则S1和S2的中
 * 位数是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能
 * 高效的算法，找出两个序列A和B的中位数。要求:
 * 1）给出算法的基本设计思想。
 * 2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 * 3）说明你所设计算法的时间复杂度和空间复杂度。
 * @return
 */

/**
 * 分别求两个升序序列A、B的中位数，设为 a 和 b，求序列 A、B 的中位数过程如下：
 * ① 若 a = b，则 a 或 b 即为所求中位数，算法结束。
 * ② 若 a<b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求两次舍弃的
 * 长度相等。
 * ③ 若 a> b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求两次舍弃的
 * 长度相等。
 */
int Search(int *A, int *B, int n) {

    int lLeft = 0, lRight = n - 1, lMid, l1Left = 0, l1Right = n - 1, l1Mid;

    while (lLeft != lRight || l1Left != l1Right){
        // 计算当前中位
        lMid = (lLeft + lRight) / 2;
        l1Mid = (l1Left + l1Right) / 2;

        // 如果符合条件①
        if (A[lMid] == B[l1Mid]) return A[lMid];

        // 如果符合条件②
        if (A[lMid] < B[l1Mid]){

            // 如果是偶数 则不需要考虑 +1
            if ((lLeft + lRight) % 2 == 0){

                // 舍去 A 小于中位数的数
                lLeft = lMid;

                // 舍去 B 大于中位数的数
                l1Right = l1Mid;
            } else{

                // 舍去 A 小于中位数的数 需凑偶
                lLeft = lMid + 1;

                l1Right = l1Mid;
            }
        }

        // 如果符合条件三
        else if (A[lMid] > B[l1Mid]){

            // 如果是偶数 则不需要考虑 +1
            if ((lLeft + lRight) % 2 == 0){

                // 舍去 B 小于中位数的数
                l1Left = l1Mid;

                // 舍去 A 大于中位数的数
                lRight = lMid;
            } else{

                // 舍去 B 小于中位数的数 需凑偶
                l1Left = l1Mid + 1;

                lRight = lMid;
            }
        }
        if (lLeft == lRight || l1Left == l1Right)

            // 此时Left和Right都已经指向最后一个元素 所以只需要进行比较 较小者为中位数
            return A[lLeft] < B[l1Left] ? A[lLeft] : B[l1Left];
    }
}

/**
 * 【2013 统考真题】已知一个整数序列A=（ao, a1,…,an-1），其中0≤ai/<n（0≤i<n）。若
 * 存在a,1=ap2= … = apm=x 且 m >n/2（0≤px<n, 1 ≤k≤m），则称ⅹ为A的主元素。例
 * 如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主
 * 元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找
 * 出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求:
 * 1）给出算法的基本设计思想。
 * 2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 * 3）说明你所设计算法的时间复杂度和空间复杂度。
 * @return
 */

int SearchMainNum(int *A, int length){
    /**
     * 1).使用主数变量和计数。假如当前值为主数，遍历数组进行count比较，大于length/2 则返回
     * 如果数组中都无此数，则返回-1
     *
     * 3).使用两个for循环，时间复杂度O(n²)，空间复杂度O(1)，据说时间复杂度占一两分，所以不需要追求时间复杂度的高效算法
     */

    // 假设主数
    int mainNum;

    // 出现次数
    int count = 0;
    while (true){
        for (int i = 0; i < length; i++) {

            // 假设当前主数值
            mainNum = A[i];
            for (int j = 0; j < length; j++){

                // 如果相等 出现次数++
                if (mainNum == A[j]) count++;
            }

            // 符合要求则返回
            if (count > length / 2) return mainNum;

            // 不符合要求 重置数据
            count = 0;
        }

        // 数组中无符合 返回 -1
        return -1;
    }
}

/**
 * 【2018统考真题】给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高
 * 效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正
 * 整数是1；数组{1,2,3}中未出现的最小正整数是4。要求:
 * 1）给出算法的基本设计思想。
 * 2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
 * 3）说明你所设计算法的时间复杂度和空间复杂度。
 * @return
 */

int mixNum(int *A, int length){
    /**
     * 1).假定最大最小值，根据题意最小正整数为1，所以首先要知道，未出现的最小正整数是否是1
     * 如果 1 已经出现，则取最大正整数 + 1
     *
     * 3).空间复杂度为O(1), 时间复杂度由于只有一次for循环，复杂度为 O(n)
     */
    int mixNum = A[0];
    int maxNum = A[0];
    for (int i = 0; i < length; i++) {

        // 假如假定的最大最小值为负数，则进行修正
        if (mixNum < 0 || maxNum < 0) {
            mixNum = A[i];
            maxNum = A[i];
            continue;
        }

        // 判断假定最小值是否是最小
        if (mixNum > A[i]){
            mixNum = A[i];
        }

        // 判断假定最大值是否是最大
        if (maxNum < A[i]){
            maxNum = A[i];
        }
    }

    // 如果最小正整数 大于 1，则说明 1 未出现过，可直接返回 1
    if (mixNum > 1)
        return mixNum - 1;
    // 如果最小正整数 1 已经存在，那么则返回当前数组最大正整数 + 1
    else
        return maxNum + 1;
}


/**
 * 【2020统考真题】定义三元组(a,b,c)（a、b、c均为正数）的距离D=|a－b|＋|b－c|+
 * |c-a|。给定 3 个非空整数集合 S1、S2和S3，按升序分别存储在 3 个数组中。请设计一
 * 个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)中
 * 的最小距离。例如 S1={-1,0,9}，S2={-25,-10,10,11}，S3={2,9,17,30,41}，则最
 * 小距离为 2，相应的三元组为(9,10,9)。要求：
 * 1）给出算法的基本设计思想。
 * 2）根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
 * 3）说明你所设计算法的时间复杂度和空间复杂度。
 * @return
 */
//2 0 -1
//3 1 3
//-1 -1 2
#define INT_MAX 0x7fffffff

int abs_(int a) {//计算绝对值
    if (a < 0)
        return -a;
    else
        return a;
}

bool xls_min(int a, int b, int c) {//a是否是三个数中的最小值
    if (a <= b && a <= c) return true;
    return false;
}

int shortestDistance(int *A, int *B, int *C, int aSize, int bSize, int cSize) {

    //D_min用于记录三元组的最小距离，初值赋为 INT_MAX
    int i = 0, j = 0, k = 0, D_min = INT_MAX, D;

    while (i < aSize && j < bSize && k < cSize && D_min > 0) {

        //计算D
        D = abs_(A[i] - B[j]) + abs_(B[j] - C[k]) + abs_(C[k] - A[i]);

        if (D < D_min)
            //更新 D
            D_min = D;

        if (xls_min(A[i], B[j], C[k]))
            //更新 a
            i++;
        else if (xls_min(B[j], C[k], A[i]))
            j++;
        else
            k++;
    }
    return D_min;
}


//int main() {
////    2
//    int a[] = {-1,0,9};
//    int b[] = {-25,-10,10,11};
//    int c[] = {2,9,17,30,41};
//    l.BatchInsert(a,3);
//    l1.BatchInsert(c,5);
//    l2.BatchInsert(b,4);
//    printf("%d",shortestDistance(l.l.data,l1.l.data,l2.l.data,l.l.length,l1.l.length,l2.l.length));
////    l.BatchInsert(a,5);
////    l1.BatchInsert(b,5);
////    printf("%d",SearchMainNum(l.l.data,8));
////    printf("%d",mixNum(l.l.data,l.l.length));
////    printf("%d",Search(l.l.data,l1.l.data,5));
//    LeftMove(1);
//    return 0;
//}